/*
 * Copyright (c) 2021
 * User:LENOVO
 * File:x的平方根.java
 * Date:2021/02/18 14:23:18
 */

package org.bytedance.拓展练习;

/**
 * 实现 int sqrt(int x) 函数。
 * <p>
 * 计算并返回 x 的平方根，其中 x 是非负整数。
 * <p>
 * 由于返回类型是整数，结果只保留整数的部分，小数部分将被舍去。
 */
public class x的平方根 {

    public static void main(String[] args) {
        x的平方根 instance = new x的平方根();
        int x = 4;
        System.out.println(instance.mySqrt(x));
        System.out.println(instance.mySqrt2(x));
        System.out.println(instance.mySqrt3(x));
        x = 8;
        System.out.println(instance.mySqrt(x));
        System.out.println(instance.mySqrt2(x));
        System.out.println(instance.mySqrt3(x));

        x = 9;
        System.out.println(instance.mySqrt(x));
        System.out.println(instance.mySqrt2(x));
        System.out.println(instance.mySqrt3(x));
    }

    /**
     * 袖珍计算器算法
     */
    public int mySqrt(int x) {
        if (x == 0) return 0;
        int res = (int) Math.exp(0.5 * Math.log(x));
        return (long) (res + 1) * (res + 1) <= x ? res + 1 : res;
    }

    /**
     * 二分查找
     */
    public int mySqrt2(int x) {
        if (x == 0 || x == 1) return x;
        int lo = 0, hi = x, res = -1;
        while (lo <= hi) {
            int mid = lo + ((hi - lo) >> 1);
            if ((long) mid * mid <= x) {
                res = mid;
                lo = mid + 1;
            } else {
                hi = mid - 1;
            }
        }
        return res;
    }

    /**
     * 牛顿迭代
     */
    public int mySqrt3(int x) {
        if (x == 0) {
            return 0;
        }
        double C = x, x0 = x;
        while (true) {
            double xi = 0.5 * (x0 + C / x0);
            if (Math.abs(x0 - xi) < 1e-7) {
                break;
            }
            x0 = xi;
        }
        return (int) x0;
    }

}
